package com.martain.leetcode.t401;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 例如，上面的二进制手表读取 “3:25”。
 *
 * 给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
 *
 *  
 *
 * 示例：
 *
 * 输入: n = 1
 * 返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
 *  
 *
 * 提示：
 *
 * 输出的顺序没有要求。
 * 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
 * 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
 * 超过表示范围（小时 0-11，分钟 0-59）的数据将会被舍弃，也就是说不会出现 "13:00", "0:61" 等时间。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-watch
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class T401 {

    /**
     * 这种解法将分钟和时钟混到一起了，所以如果 n>=4 的时候 可能有情况 32 16 8 4 为 60 分钟，也就是1:00 但是这个是不准确的。 就是没有进位
     */

    LinkedList<Integer> minutes = new LinkedList<Integer>(){
        {
            add(480);
            add(240);
            add(120);
            add(60);
            add(32);
            add(16);
            add(8);
            add(4);
            add(2);
            add(1);
        }
    };

    int time = 0;
    LinkedList<String> result = new LinkedList<>();
    public List<String> readBinaryWatch(int num) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(num,track);
        Collections.reverse(result);
        if (num>=4){
            result.remove("1:00");
        }
        return result;
    }

    public void backtrack(int n,LinkedList<Integer> track){
        if (n==0){
            String timeString = minute2timeString(time);
            if (!result.contains(timeString))
            {
                result.add(timeString);
            }
            return;
        }
        int size = minutes.size();
        for (int i = 0; i < size; i++) {
            Integer minute = minutes.get(i);
            if (!check(minute+time) || track.contains(minute)){
                continue;
            }
            time = time + minute;
            track.add(minute);
            backtrack(n-1,track);
            track.removeLast();
            time = time - minute;
        }


    }

    public boolean check(int time){
        return time >= 0 && time <= 719;
    }

    public String minute2timeString(int minuteNumber){
        int hour = minuteNumber/60;
        int minute = minuteNumber%60;
        if (minute<10){
            return hour+":0"+minute;
        }
        return hour+":"+minute;
    }

    public static void main(String[] args) {
        T401 t401 = new T401();
        List<String> strings = t401.readBinaryWatch(4);
        System.out.println(strings);
    }
}
